package style.zcyLeetCode.a_0003_详解桶排序以及排序内容大总结;

import java.util.Arrays;
import java.util.PriorityQueue;

public class SortArrayDistanceLessK {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 5, 4, 2};
        sortedArrDistanceLessK(arr, 2);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 知识点：PriorityQueue优先级队列为小顶堆
     * @param arr
     * @param k
     */
    public static void sortedArrDistanceLessK(int[] arr, int k) {
        // 默认小顶堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        // 先把k位数丢进小顶堆中
        int index = 0;
        for (; index <= Math.min(arr.length, k); index++) {
            heap.add(arr[index]);
        }

        // 依次循环遍历数组，每次add进去index后的数，并且poll掉前面的数，保证heap里面最大只有k+1个数
        int i = 0;
        for (; index < arr.length; i++, index++) {
            heap.add(arr[index]);
            arr[i] = heap.poll();
        }

        // 当小顶堆不为空时，从头开始追加进arr数组的后面。
        while (!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }
    }
}
